package bintree.heap.LeetCode;
//面试题 17.14. 最小K个数

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
//设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

/**
 * 最简单的办法就是用快速排序，然后保存前k个
 */
//public class Num17_14_smallestK {
//    public int[] smallestK(int[] arr, int k) {
//        Arrays.sort(arr); //快速排序
//        int[] data = new int[k];
//        for (int i = 0; i < k; i++) {
//             data[i] = arr[i];
//        }
//    return data;
//    }
//}

/**
 * 思路二：用优先级队列
 */

/*

//创建一个类 比较器
class Integerreverse implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        //这样反过来写，就是降序，最大堆
        return o2 - o1;
    }
}

public class Num17_14_smallestK {
    public int[] smallestK(int[] arr, int k) {
       int[] ret = new int[k];

        //边界--因为就算不存在也要返回空数组
       if(arr.length == 0 || k == 0){
           return ret;
       }
        //此时我们只能用java提供的优先级队列
        //但 JDK默认提供的是一个最小堆，我们需要的是大堆
        //就需要改造成大堆
        //这是匿名内里类的创建方法
//        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                //这样反过来写，就是降序，最大堆
//                return o2 - o1;
//            }
//        });

        Queue<Integer> queue = new PriorityQueue<>(new Integerreverse());
        //遍历原数组集合，队列中保存k个元素
        for(int i : arr){

            //判断队列是有 k 个元素
            if(queue.size() < k){
                //说明此时队列没有k个元素，就添加
                queue.offer(i);
            }else{
                //说明此时队列不需要继续增加元素了
                int max = queue.peek();//查看树顶元素
                if(max > i){
                    queue.poll();//弹出树顶元素
                    queue.offer(i);//添加max，同时进行下层操作

                }
            }

        }
        //此时队列里面就保存了最小的k个元素，依次出队就行
        int t = 0;
        while(!queue.isEmpty()){
            ret[t ++] = queue.poll();
        }

        return ret;
    }
}

 */

/**
 * 思路三：使用匿名内部类
 */

public class Num17_14_smallestK {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];

        //边界--因为就算不存在也要返回空数组
        if(arr.length == 0 || k == 0){
            return ret;
        }
        //此时我们只能用java提供的优先级队列
        //但 JDK默认提供的是一个最小堆，我们需要的是大堆
        //就需要改造成大堆

        //这是匿名内里类的创建方法
//        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                //这样反过来写，就是降序，最大堆
//                return o2 - o1;
//            }
//        });

        //在匿名内部类更简单的写法
        // Lambda表达式  等价的
        Queue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);

        //遍历原数组集合，队列中保存k个元素
        for(int i : arr){

            //判断队列是有 k 个元素
            if(queue.size() < k){
                //说明此时队列没有k个元素，就添加
                queue.offer(i);
            }else{
                //说明此时队列不需要继续增加元素了
                int max = queue.peek();//查看树顶元素
                if(max > i){
                    queue.poll();//弹出树顶元素
                    queue.offer(i);//添加max，同时进行下层操作

                }
            }

        }
        //此时队列里面就保存了最小的k个元素，依次出队就行
        int t = 0;
        while(!queue.isEmpty()){
            ret[t ++] = queue.poll();
        }

        return ret;
    }
}
